The present invention relates to memory systems in general, and specifically to memory systems incorporating linked lists.
Often within a data processing system multiple processors and devices will access a common memory space. In such a case, it is necessary to coordinate the use and allocation of addresses within the common memory space so that each device addresses unique locations and avoids interference. For example, in a telecommunication switching system, such as an asynchronous transfer mode application (ATM), where multiple data ports share a the common memory space. One method of coordinating addresses involves the use of a linked list. The linked list is a copy of the common memory space, having a pointer associated with each memory address. Each device in the system has a list containing data to be stored in the data memory. The pointers indicate where the contents of the list are located in data memory.
The list pointers are compiled into a table, which may be maintained in software or in hardware. A list is typically designated as having a starting address, known as the xe2x80x9cheadxe2x80x9d of the list, and an ending address, known as the xe2x80x9ctailxe2x80x9d of the list. The addresses between the head and tail are not necessarily sequential, and are typically spread throughout data memory. The list pointer then keeps track of all of the addresses that are contained within the list.
When the lists are implemented in hardware, control logic is used to update the list pointer, and to interface with the memory. Often this control logic will be some type of an application specific integrated circuit (ASIC) device which is specially designed and separate from the memory integrated circuit. ASIC solutions do not typically optimize access speed, and are expensive.
When designating addresses within a memory space it is desirable to use the entire memory space. Software implementations increase memory processing time, creating a problem in many faster memories. While it is desirable to implement these memory systems in hardware so as to increase the speed of memory access needed in fast memories, the linked list method may not always utilize all of the addresses within the memory.
There is a need for a linked list memory which provides the speed of a hardware implementation, while ensuring that all addresses within the main memory have been used.